#include<stdio.h>


struct ElemType{
	int key;
};

void QuickSort(ElemType A[], int low, int high);
int QuickPass(ElemType A[], int low, int high);

int main(){
	ElemType A[5] = {{2},{1},{6},{4},{9}};
	QuickSort(A, 0, 4);
	for(int i=0;i<=4;i++){
		printf("%d\n", A[i]);
	}
	
	ElemType B[10000];
	for(int i=0;i<=9999;i++){
		B[i].key = i % 1000 + i * 2 - i % 10;
	}
	for(int i=0;i<=9999;i++){
		printf("%d\n", B[i]);
	}

}


void QuickSort(ElemType A[], int low, int high){
	int pivot;
	if(low >= high){
		return;
	}
	pivot = QuickPass(A, low, high);
	QuickSort(A, low, pivot-1);
	QuickSort(A, pivot+1, high);
}
int QuickPass(ElemType A[], int low, int high){
	ElemType x = A[low];
	while (low < high){
		while(low < high && x.key <= A[high].key){
			high--;
		}
		if(low == high){
			break;
		}
		A[low++] = A[high];
		while (low < high && x.key >= A[low].key){
			++low;
		}
		if (low == high){
			break;
		}
		A[high--] = A[low];
	}
	A[low] = x;
	return low;
}
